import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

public class MySort {
    int[] arr = {1,3,5};
    int useSize = 3;
    int[] arr2 = {1,2,2,1,3,4,5,3,3};
    int[] arr3 = {2,2,1,4,1};
    int[] arr4 = new int[10];
    public void createArr(){
        Random random = new Random();
        for (int i = 0; i < arr4.length; i++) {
            arr4[i] = random.nextInt(100);
        }
    }
    public MySort(){

    }
    public boolean isFull(){
        return arr.length == useSize;
    }
    public void insertSort(int val){
        if (isFull()){
            arr = Arrays.copyOf(arr,arr.length*2);
        }
        arr[useSize] = val;
        int index = useSize;
        for (int i = useSize-1; i >= 0; i--) {
            if (arr[i] > arr[index]) {
                int tmp = arr[i];
                arr[i] = arr[index];
                arr[index] = tmp;
                index--;
            }else {
                break;
            }
        }
        useSize++;
    }
    public void insertSort2(){
        for (int i = 1; i < arr2.length; i++) {
            int j;
            int tmp = arr2[i];
            for (j = i-1; j >= 0 ; j--) {
                if (arr2[j] > tmp){
                   arr2[j+1] = arr2[j];
                }else {
                    break;
                }
            }
            arr2[j+1] = tmp;
        }
    }
    public void shellSort(int gap){
        for (int i = gap; i <arr2.length ; i++) {
            int tmp = arr2[i];
            int j;
            for (j = i-gap; j >=0 ; j-=gap) {
                if (arr2[j] > tmp){
                    arr2[j+gap] = arr2[j];
                }else {
                    break;
                }
            }
            arr2[j+gap] = tmp;
        }
    }
    public void selectSort(){
        for (int i = 0; i < arr3.length; i++) {
            int tmp = arr3[i];
            int t = i;
            for (int j = i+1; j < arr3.length; j++) {
                if (tmp > arr3[j]){
                    tmp = arr3[j];
                    t = j;
                }
            }
            arr3[t] = arr3[i];
            arr3[i] = tmp;

        }
    }
    public void selectSort2(){
        for (int i = 0; i < arr3.length; i++) {
            int t = i;
            for (int j = i+1; j < arr3.length; j++) {
                if (arr3[t] > arr3[j]){
                    t = j;
                }
            }
            int tmp = arr3[t];
            arr3[t] = arr3[i];
            arr3[i] = tmp;

        }
    }
    public void shiftDown(int len,int p){
        int child = p*2 + 1;
        while (child < len){
            if (child+1 < len && arr3[child+1] > arr3[child]){
                child++;
            }
            if (arr3[p] < arr3[child]){
                    int tmp = arr3[p];
                    arr3[p] = arr3[child];
                    arr3[child] = tmp;
                    p = child;
                    child = child*2+1;
            }else {
                break;
            }
        }
    }
    public void createTree(){
        int len = arr3.length;
        int p = (len-2)/2;
        for (int i = p; i >=0 ; i--) {
            shiftDown(len,i);
        }
    }
    public void puPrint(){
        int len = arr3.length;
        while ((len-2)/2 >= 0){
            int tmp = arr3[len-1];
            arr3[len-1] = arr3[0];
            arr3[0] = tmp;
            len--;
            shiftDown(len,0);
        }
    }
    //快速排序
    public void swap(int left,int right){
        int tmp = arr3[left];
        arr3[left] = arr3[right];
        arr3[right] = tmp;

    }
    public void swap4(int left,int right){
        int tmp = arr4[left];
        arr4[left] = arr4[right];
        arr4[right] = tmp;

    }
    //
    public int selectPero(int left,int right){
        int tmp = arr3[left];
        int ret = left;
        while (left < right){
           while (left < right){
               if (arr3[right] >= tmp){
                   right--;
               }else {
                   break;
               }
           }
            while (left < right){
                if (arr3[left] <= tmp){
                    left++;
                }else {
                    break;
                }
            }
            swap(left,right);
        }
        swap(ret,right);
        return left;
    }
    public void quickSort(int[] arr,int left,int right){
        if (left >= right){
            return;
        }
        int pero = selectPero(left,right);
        quickSort(arr,left,pero-1);
        quickSort(arr,pero+1,right);
    }
    //挖坑法
    public int selectPero2(int left,int right){
        int tmp = arr3[left];
        while (left < right){
            while (left < right && arr3[right] >= tmp){
                    right--;
            }
            arr3[left] = arr3[right];
            while (left < right && arr3[left] <= tmp){
                left++;
            }
            arr3[right] = arr3[left];
        }
        arr3[left] = tmp;
        return left;
    }
    public void digQuickSort(int[] arr3,int left,int right){
        if (left >= right){
            return;
        }
        int pero = selectPero2(left,right);
        digQuickSort(arr,left,pero-1);
        digQuickSort(arr,pero+1,right);
    }
    //前后指针法
    public int selectPero3(int left,int right){
        int pero = left;
        int cur = left+1;
        while (cur <= right){
            if (arr3[cur] < arr3[left] && ++pero != cur){
                swap(pero,cur);
            }
            cur++;
        }
        swap(pero,left);
        return pero;
    }
    public void pointerSort(int[] arr3,int left,int right){
        if (left >= right){
            return;
        }
        int pero = selectPero3(left,right);
        pointerSort(arr3,left,pero-1);
        pointerSort(arr3,pero+1,right);
    }
    //优化前后指针法
    public int selectPero4(int left,int right){
        int pero = left;
        int cur = left+1;
        while (cur <= right){
            if (arr4[cur] < arr4[left] && (++pero) != cur){
                swap4(pero,cur);
            }
            cur++;
        }
        swap4(pero,left);
        return pero;
    }
    public int op(int left,int right){
        int main = (left+right)/2;
        if (arr4[left] < arr4[right]){
            if (arr4[main] < arr4[left]){
                return left;
            }else if (arr4[main] > arr4[right]){
                return right;
            }else {
                return main;
            }
        }else {
            if (arr4[main] > arr4[left]){
                return left;
            }else if(arr4[main] < arr4[right]){
                return right;
            }else {
                return main;
            }
        }
    }
    public void pointerSort4(int[] arr4,int left,int right){
        if (left >= right){
            return;
        }
        int tmp = op(left,right);
        swap4(left,tmp);
        int pero = selectPero4(left,right);
        pointerSort4(arr4,left,pero-1);
        pointerSort4(arr4,pero+1,right);
    }
    //非递归快速排序
    public int noPero(int left,int right){
        int tmp = arr4[left];
        while (left < right){
            while (left < right){
                if (arr4[right] >= tmp){
                    right--;
                }else {
                    arr4[left] = arr4[right];
                }
                if (arr4[left] <= tmp){
                    left++;
                }else {
                    arr4[right] = arr4[left];
                }
            }
        }
        arr4[right] = tmp;
        return right;
    }
    public void noSort(){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = arr4.length-1;
        if (left >= right) return;
        int pero = noPero(left,right);
        if (pero > left + 1){
            stack.push(left);
            stack.push(pero-1);
        }
        if (pero + 1 < right){
            stack.push(pero + 1);
            stack.push(right);
        }
        while (!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            pero = noPero(left,right);
            if (pero > left + 1){
                stack.push(left);
                stack.push(pero-1);
            }
            if (pero + 1 < right){
                stack.push(pero + 1);
                stack.push(right);
            }
        }
    }
    //归并排序
    //归并函数
    public void merge(int left,int center,int right){
        int s1 = left;
        int e1 = center;
        int s2 = center+1;
        int e2 = right;
        int i = 0;
        int[] tmp = new int[right-left+1];
       while (s1 <= e1 && s2 <= e2){
           if (arr4[s1] <= arr4[s2]){
               tmp[i++] = arr4[s1++];
           }else {
               tmp[i++] = arr4[s2++];
           }
       }
       while (s1 <= e1){
           tmp[i++] = arr4[s1++];
       }
        while (s2 <= e2){
            tmp[i++] = arr4[s2++];
        }
        for (int j = 0; j < tmp.length; j++) {
            arr4[j+left] = tmp[j];
        }
    }
    //拆分函数
    public void split(int left,int right){
        if (left >= right) return;
        int centre = (left+right)/2;
        split(left,centre);
        split(centre+1,right);
        merge(left,centre,right);

    }
    public void mergeSort(){
        int left = 0;
        int right = arr4.length-1;
        split(left,right);
    }
    //非递归归并函数
    public void noRecursionSplit(int left,int right){
        int gap = 1;
        while (gap < right){
            for (int i = left; i < right+1; i += gap*2) {
                int center = i + gap -1;
                //修正
                if (center > right){
                    center = right;
                }
                int height = center + gap;
                //修正
                if (height > right){
                    height = right;
                }
                merge(i,center,height);
            }
            gap *= 2;
        }
    }
    public void noRecursion(){
        int left = 0;
        int right = arr4.length-1;
        noRecursionSplit(left,right);
    }
}
